# 弗洛伊德

# 弗洛伊德算法的实现思路
# 弗洛伊德算法查找图 1 中各个顶点之间的最短路径，实现过程如下：
# 1) 建立一张表格，记录每个顶点直达其它所有顶点的权值：
"""
表 1 各个顶点直达路径的权值
                        目标顶点
--------------------------------------------
            1	    2	    3	     4
起始顶点
--------------------------------------------
        1	    0	    3	    ∞	    5
    2	    2	    0	    ∞	    4
    3	    ∞	   1	   0	    ∞
    4	    ∞	   ∞	  2	       0
--------------------------------------------

"""
# 2) 在表 1 的基础上，将顶点 1 作为 "中间顶点"，计算从各个顶点出发途径顶点 1 再到达其它顶点的权值，如果比表 1 中记录的权值更小，证明两个顶点之间存在更短的路径，对表 1 进行更新。

# 从各个顶点出发，途径顶点 1 再到达其它顶点的路径以及对应的权值分别是：
"""
2-1-3：权值为 2 + ∞ = ∞，表 1 中记录的 2-3 的权值也是 ∞；
2-1-4：权值为 2 + 5 = 7，表 1 中记录的 2-4 的权值是 4；
3-1-2：权值为 ∞ + 3，表 1 中记录的 3-2 的权值是 1；
3-1-4：权值为 ∞ + 5，表 1 中记录的 3-4 的权值是 ∞；
4-1-2：权值为 ∞ + 3，表 1 中记录的 4-2 的权值是 ∞；
4-1-3：权值为 ∞ + ∞，表 1 中记录的 4-3 的权值是 2。

以上所有的路径中，没有比表 1 中记录的权值最小的路径，所以不需要对表 1 进行更新。
"""

# 3) 在表 1 的基础上，以顶点 2 作为 "中间顶点"，计算从各个顶点出发途径顶点 2 再到达其它顶点的权值：
"""
1-2-3：权值为 3 + ∞，表 1 中记录的 1-3 的权值为 ∞；
1-2-4：权值为 3 + 4 = 7，表 1 中 1-4 的权值为 5；
3-2-1：权值为 1 + 2 = 3，表 1 中 3-1 的权值为 ∞，3 < ∞；
3-2-4：权值为 1 + 4 = 5，表 1 中 3-4 的权值为 ∞，5 < ∞；
4-2-1：权值为 ∞ + 2，表 1 中 4-1 的权值为 ∞；
4-2-3：权值为 ∞ + ∞，表 1 中 4-3 的权值为 2。

以顶点 2 作为 "中间顶点"，我们找到了比 3-1、3-4 更短的路径，对表 1 进行更新：
表 2 更新后的 "表 1"
 	                目标顶点
------------------------------------------------------------------------                     
                    1	           2	     3	         4
起始顶点	
------------------------------------------------------------------------                     
1	                0	           3	     ∞	        5
2	                2	           0	     ∞	        4
3	                3（3-2-1）	   1	     0	         5（3-2-4）
4	                ∞	          ∞	       2	        0
------------------------------------------------------------------------                     

"""


# 4) 在表 2 的基础上，将顶点 3 作为 "中间顶点"，计算从各个顶点出发途径顶点 3 再到达其它顶点的权值：
"""
1-3-2 权值为 ∞ + 1，表 2 中 1-2 的权值为 3；
1-3-4 权值为 ∞ + 5，表 2 中 1-4 的权值为 5；
2-3-1 权值为 ∞ + 3，表 2 中 2-1 的权值为 2；
2-3-4 权值为 ∞ + 5，表 2 中 2-4 的权值为 4；
4-3-1 权值为 2 + 3 = 5，表 2 中 4-1 的权值为 ∞，5 < ∞；
4-3-2 权值为 2 + 1 = 3，表 2 中 4-2 的权值为 ∞，3 < ∞；

以顶点 3 作为 "中间顶点"，我们找到了比 4-1、4-2 更短的路径，对表 2 进行更新：

表 3 更新后的 "表 2"
 	                目标顶点
------------------------------------------------------------------------                     
                1	            2	            3	        4
起始顶点	
------------------------------------------------------------------------                     
1	            0	            3	            ∞	        5
2	            2	            0	            ∞	        4
3	            3（3-2-1）	    1	            0	         5（3-2-4）
4	            5（4-3-2-1）	3（4-3-2）	    2	         0
------------------------------------------------------------------------                     
"""


# 5) 在表 3 的基础上，将顶点 4 作为 "中间顶点"，计算从各个顶点出发途径顶点 4 再到达其它顶点的权值：
"""
1-4-2 权值为 5 + 3 = 8，表 3 中 1-2 的权值为 3；
1-4-3 权值为 5 + 2 = 7，表 3 中 1-3 的权值为 ∞，7 < ∞；
2-4-1 权值为 4 + 5 = 9，表 3 中 2-1 的权值为 2；
2-4-3 权值为 4 + 2 = 6，表 3 中 2-3 的权值为 ∞，6 < ∞；
3-4-1 权值为 4 + 5 = 9，表 3 中 3-1 的权值为 3；
3-4-2 权值为 5 + 5 = 10 ，表 3 中 3-2 的权值为 1。

以顶点 4 作为 "中间顶点"，我们找到了比 1-3、2-3 更短的路径，对表 3 进行更新：

表 4 更新后的 "表 3"
 	                目标顶点
------------------------------------------------------------------------                     
                1	            2	            3	            4
起始顶点	
------------------------------------------------------------------------                     
1	            0	            3	            7（1-4-3）	    5
2	            2	            0	            6（2-4-3）	    4
3	            3（3-2-1）	    1	            0	            5（3-2-4）
4	            5（4-3-2-1）	3（4-3-2）	    2	            0
------------------------------------------------------------------------            

                            目标顶点       目标顶点        目标顶点       目标顶点
                            1	            2	            3	            4
起始顶点    1	            0	            3	            7（1-4-3）	    5
起始顶点    2	            2	            0	            6（2-4-3）	    4
起始顶点    3	            3（3-2-1）	    1	            0	            5（3-2-4）
起始顶点    4	            5（4-3-2-1）	3（4-3-2）	    2	            0

+----------+---+--------------+------------+------------+------------+
|          |  ​ |   目标顶点   |  目标顶点​  |  目标顶点​​  |  目标顶点​​​  |
+----------+---+--------------+------------+------------+------------+
|          |   |      1       |     2      |     3      |     4      |
| 起始顶点 | 1 |      0       |     3      | 7（1-4-3） |     5      |
| 起始顶点 | 2 |      2       |     0      | 6（2-4-3） |     4      |
| 起始顶点 | 3 |  3（3-2-1）  |     1      |     0      | 5（3-2-4） |
| 起始顶点 | 4 | 5（4-3-2-1） | 3（4-3-2） |     2      |     0      |
+----------+---+--------------+------------+------------+------------+

+----------+---+--------------+------------+------------+------------+
|    #     | @ |  目标顶点1   | 目标顶点2  | 目标顶点3  | 目标顶点4  |
+----------+---+--------------+------------+------------+------------+
|          |   |      1       |     2      |     3      |     4      |
| 起始顶点 | 1 |      0       |     3      | 7（1-4-3） |     5      |
| 起始顶点 | 2 |      2       |     0      | 6（2-4-3） |     4      |
| 起始顶点 | 3 |  3（3-2-1）  |     1      |     0      | 5（3-2-4） |
| 起始顶点 | 4 | 5（4-3-2-1） | 3（4-3-2） |     2      |     0      |
+----------+---+--------------+------------+------------+------------+

+----------+---------+--------------+------------+------------+------------+
| Field 1  | Field 2 |   Field 3    |  Field 4   |  Field 5   |  Field 6   |
+----------+---------+--------------+------------+------------+------------+
|          |         |      1       |     2      |     3      |     4      |
| 起始顶点 |    1    |      0       |     3      | 7（1-4-3） |     5      |
| 起始顶点 |    2    |      2       |     0      | 6（2-4-3） |     4      |
| 起始顶点 |    3    |  3（3-2-1）  |     1      |     0      | 5（3-2-4） |
| 起始顶点 |    4    | 5（4-3-2-1） | 3（4-3-2） |     2      |     0      |
+----------+---------+--------------+------------+------------+------------+
"""


# 通过将所有的顶点分别作为“中间顶点”，
# 最终得到的表 4 就记录了各个顶点之间的最短路径。例如，4-1 的最短路径为 4-3-2-1。

V = 4  # 顶点的个数
INF = 65535  # 设定一个最大值
P = [[0] * V for i in range(V)]  # 记录各个顶点之间的最短路径
# 有向加权图中各个顶点之间的路径信息
graph = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF], [INF, INF, 2, 0]]


# 中序递归输出各个顶点之间最短路径的具体线路
def printPath(i, j):
    k = P[i][j]
    if k == 0:
        return
    printPath(i, k)
    print("%d-" % (k + 1), end="")
    printPath(k, j)


# 输出各个顶点之间的最短路径
def printMatrix(graph):
    for i in range(V):
        for j in range(V):
            if j == i:
                continue
            print("%d - %d: 最短路径为:" % (i + 1, j + 1), end="")
            if graph[i][j] == INF:
                print("INF")
            else:
                print(graph[i][j], end="")
                print("，依次经过：%d-" % (i + 1), end="")
                # 调用递归函数
                printPath(i, j)
                print(j + 1)


# 实现弗洛伊德算法,graph[][V] 为有向加权图
def floydWarshall(graph):
    # 遍历每个顶点，将其作为其它顶点之间的中间顶点，更新 graph 数组
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # 如果新的路径比之前记录的更短，则更新 graph 数组
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    # 记录此路径
                    P[i][j] = k
    # 输出各个顶点之间的最短路径
    printMatrix(graph)


floydWarshall(graph)
